#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "TypeDefin.h"
using namespace std;
/*HJJ QQ479287006
 *小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。

给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

 

示例 1:



输入: root = [3,2,3,null,3,null,1]
输出: 7
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/house-robber-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */
//很明显先层次遍历 再DP就复杂了
int rob(TreeNode* root) {



}

//递归解法
//int rob(TreeNode* root) {
//    if (root == NULL) return 0;
//    if (root->left == NULL && root->right == NULL) return root->val;
//// 偷⽗节点
//    int val1 = root->val;
//    if (root->left) val1 += rob(root->left->left) + rob(root->left->right);
//// 跳过root->left，相当于不考虑左孩⼦了
//    if (root->right) val1 += rob(root->right->left) + rob(root->right-
//                                                          >right); // 跳过root->right，相当于不考虑右孩⼦了
//// 不偷⽗节点
//    int val2 = rob(root->left) + rob(root->right); // 考虑root的左右孩⼦
//    return max(val1, val2);
//}

//记忆化递归 这道题记忆化递归反而更好
//unordered_map<TreeNode* , int> umap; // 记录计算过的结果
//int rob(TreeNode* root) {
//    if (root == NULL) return 0;
//    if (root->left == NULL && root->right == NULL) return root->val;
//    if (umap[root]) return umap[root]; // 如果umap⾥已经有记录则直接返回
//// 偷⽗节点
//    int val1 = root->val;
//    if (root->left) val1 += rob(root->left->left) + rob(root->left->right);
//// 跳过root->left
//
//    if (root->right) val1 += rob(root->right->left) + rob(root->right->right); // 跳过root->right
//// 不偷⽗节点
//    int val2 = rob(root->left) + rob(root->right); // 考虑root的左右孩⼦
//    umap[root] = max(val1, val2); // umap记录⼀下结果
//    return max(val1, val2);
//}


int rob(TreeNode* root) {
    if (root== nullptr)
        return 0;
    if (!root->left&&!root->right)
        return root->val;

    int val1=root->val;

    if (root->left)
    {
        val1+=rob(root->left->left)+rob(root->left->right);
    }

    if (root->right)
    {
        val1+=rob(root->right->left)+rob(root->right->right);
    }

    int val2=rob(root->right)+rob(root->left);


    return max(val1,val2)

}